package com.example.leetdemo.process;

import java.util.*;

public class Solution207 {
    public static void main(String[] args) {
        Solution207 solution207 = new Solution207();
        System.err.println(solution207.canFinish(8, new int[][] {
                {1,0}, {2, 6}, {1, 7}, {6, 4}, {7, 0}, {0, 5}
        }));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<int[]>> integerMap = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            if (integerMap.get(prerequisites[i][0]) == null) {
                List<int[]> list = new ArrayList<>();
                list.add(prerequisites[i]);
                integerMap.put(prerequisites[i][0], list);
            } else {
                List<int[]> list = integerMap.get(prerequisites[i][0]);
                list.add(prerequisites[i]);
                integerMap.put(prerequisites[i][0], list);
            }
        }
        Set<Integer> set = new HashSet<>();
        set.add(0);
        if (!dps(set, integerMap, 0)) {
            return false;
        }
        for (int i = 1; i < numCourses; i++) {
            if (!set.contains(i)) {
                if (!dps(set, integerMap, i)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean dps(Set<Integer> integerSet, Map<Integer, List<int[]>> map, int nowKey) {
        List<int[]> now = map.get(nowKey);
        if (now == null) {
            integerSet.remove(nowKey);
            return true;
        }
        for (int i = 0; i < now.size(); i++) {
            if (integerSet.contains(now.get(i)[1])) {
                return false;
            }
            integerSet.add(now.get(i)[1]);
            if (!dps(integerSet, map, now.get(i)[1])) {
                return false;
            }
        }
        integerSet.remove(nowKey);
        return true;
    }


    private boolean dps2(Set<Integer> integerSet, Map<Integer, List<int[]>> map, int nowKey) {
        List<int[]> now = map.get(nowKey);
        if (now == null) {
            integerSet.remove(nowKey);
            return true;
        }
        for (int i = 0; i < now.size(); i++) {
            if (integerSet.contains(now.get(i)[1])) {
                return false;
            }
            integerSet.add(now.get(i)[1]);
            if (!dps2(integerSet, map, now.get(i)[1])) {
                return false;
            }
        }
        return true;
    }
}
